package 二叉树;
import java.util.*;
/**
 * 寻找二叉树的最近公共祖先
 * 时间复杂度O(n)，空间复杂度O(h)，n为节点个数，h为树的高度
 */
public class lowestCommonAncestor {
    /**
     * 二叉树节点类
     * 包含节点值、左子节点和右子节点
     */
    public static class TreeNode{
        int val;            // 节点值
        TreeNode left;      // 左子节点
        TreeNode right;     // 右子节点
        
        // 无参构造函数
        TreeNode(){}
        
        // 带值的构造函数
        TreeNode(int val){
            this.val = val;
        }
        
        // 带值、左子节点和右子节点的构造函数
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 寻找二叉树的最近公共祖先
     * 使用递归方法，判断当前节点是否为p或q的祖先
     * 
     * @param root 二叉树的根节点
     * @param p 第一个节点
     * @param q 第二个节点
     * @return 最近公共祖先节点
     */
    public static TreeNode lowestCommonAncestorM(TreeNode root, TreeNode p, TreeNode q){
        if(root == null) return null; // 如果根节点为空，返回null
        if(root == p) return p; // 如果根节点为p，返回p
        if(root == q) return q; // 如果根节点为q，返回q
        TreeNode left = lowestCommonAncestorM(root.left, p , q); // 递归查找左子树
        TreeNode right = lowestCommonAncestorM(root.right, p, q); // 递归查找右子树
        if(left != null && right != null) return root; // 如果左右子树都找到，返回根节点
        return left != null ? left : right; // 返回左子树或右子树的结果
    }

    /**
     * 根据层序遍历的字符串数组构建二叉树
     * 使用队列进行层序遍历构建
     * 
     * @param nodes 层序遍历的节点值数组，"null"表示空节点
     * @return 构建好的二叉树根节点
     */
    public static TreeNode buildTree(String[] nodes){
        if(nodes.length == 0 || nodes == null || nodes[0].equals("null"))
            return null; // 如果输入数组为空或根节点为null，返回null
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0])); // 创建根节点
        queue.offer(root); // 将根节点加入队列
        int index = 1; // 从第二个节点开始处理
        while(!queue.isEmpty() && index < nodes.length){ // 当队列不为空且未处理完所有节点时，继续构建
            TreeNode cur = queue.poll(); // 取出队首节点
            if(index < nodes.length && !nodes[index].equals("null")){ // 如果左子节点不为null
                cur.left = new TreeNode(Integer.parseInt(nodes[index])); // 创建左子节点
                queue.offer(cur.left); // 将左子节点加入队列
            }
            index++; // 处理下一个节点
            if(index < nodes.length && !nodes[index].equals("null")){ // 如果右子节点不为null
                cur.right = new TreeNode(Integer.parseInt(nodes[index])); // 创建右子节点
                queue.offer(cur.right); // 将右子节点加入队列
            }
            index++; // 处理下一个节点
        }
        return root; // 返回构建好的二叉树根节点
    }

    /**
     * 在二叉树中查找指定值的节点
     * 使用递归方法，遍历二叉树查找目标节点
     * 
     * @param root 二叉树的根节点
     * @param val 目标节点的值
     * @return 目标节点，如果未找到返回null
     */
    public static TreeNode findNode(TreeNode root, int val){
        if(root == null) return null; // 如果根节点为空，返回null
        if(root.val == val) return root; // 如果当前节点为目标节点，返回当前节点
        TreeNode left = findNode(root.left, val); // 递归查找左子树
        TreeNode right = findNode(root.right, val); // 递归查找右子树
        return left != null ? left : right; // 返回左子树或右子树的结果
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一行数字，用空格分隔，表示二叉树的层序遍历，"null"表示空节点
     * 例如：3 9 20 null null 15 7 表示一个二叉树
     * 输出格式：最近公共祖先节点的值
     */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] nodes = sc.nextLine().split(" "); // 读取输入并分割
        TreeNode root = buildTree(nodes); // 构建二叉树
        int pval = sc.nextInt(); // 读取第一个节点的值
        TreeNode p = findNode(root, pval); // 查找第一个节点
        int qval = sc.nextInt(); // 读取第二个节点的值
        TreeNode q = findNode(root, qval); // 查找第二个节点
        System.out.println(lowestCommonAncestorM(root, p, q).val); // 输出最近公共祖先节点的值
        sc.close(); // 关闭输入流
    }
}
